package com.markus.code.动态规划;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/16 16:49
 * todo: 过河问题
 */
public class Class04_ThroughRiver {
    /**
     * 给定一个数组arr，长度为N且每个值都是正数，代表N个人的体重。再给定一个正数
     * limit，代表一艘船的载重。
     * 以下是坐船规则，1)每艘船最多只能做两人;2)乘客 的体重和不能超过limit。
     * 返回如果同时让这N个人过河最少需要几条船。
     */
    public int throughRiver(int []arr,int limit){
        if (arr == null || arr.length==0 || limit <=0){
            return 0;
        }
        /**
         * 这个题的思想就是：找到小于等于 limit/2 的最右边的数字，
         * 然后分别往左右遍历，找到能组合乘船的情况
         */
        if (arr[arr.length-1] > limit){
            return -1;
        }
        //最右边的小于等于 limit/2的指针
        int lessRight = -1;
        for (int i=arr.length-1;i>=0;i--){
            if (arr[i] <= (limit/2)){
                lessRight = i;
                break;
            }
        }
        if (lessRight == -1){
            return arr.length;
        }
        int L = lessRight;
        int R = lessRight+1;
        int use = 0;
        while(L >= 0 && R < arr.length){
            int zuHeOk = 0;
            while(R < arr.length && arr[L] + arr[R] <= limit){
                zuHeOk ++ ;
                R ++ ;
            }
            if (zuHeOk == 0){
                L -- ;
            }else if (L - zuHeOk  >= 0){
                use += zuHeOk;
                L = L - zuHeOk ;
            }else{
                use += L+1;
                L = -1;
            }
        }
        //经历一遍循环，数组中有多少能够组合的就已经知道了。
        int noUse = lessRight+1-use;
        int ans = use + (noUse+1>>1) + arr.length-1-lessRight-use;
        return ans;
    }

    public static void main(String[] args) {
//        int arr[] = {2,2,3,3,5,5,6,7};
//        int arr[] = {3,5,5,6,7};
        int arr[] = {1,2,3,3,5,5,6,7,8,9};
        int limit = 10;
        Class04_ThroughRiver demo = new Class04_ThroughRiver();
        System.out.println(demo.throughRiver(arr,limit));
    }
}
